package com.uyong.study.datastruct;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 无向图（邻接链表实现）
 * 
 * @author gonggy
 * @since 2019-02-21
 */
public class Graph {

	/** 顶点个数 */
	private int v;
	/** 邻接表 */
	private LinkedList<Integer> adj[];

	@SuppressWarnings("unchecked")
	public Graph(int v) {
		this.v = v;
		adj = new LinkedList[v];
		Arrays.setAll(adj, (i) -> new LinkedList<>());
	}

	public Integer[] get(int i) {
		return adj[i].toArray(new Integer[0]);
	}

	/**
	 * 加入一条边
	 * 
	 * @param s 边的顶点
	 * @param t 边的另一个顶点
	 */
	public void addEdge(int s, int t) {
		adj[s].add(t);
		adj[t].add(s);
	}

	/**
	 * 广度优先搜索算法，时间复杂度O(E),E表示边的个数
	 * 
	 * @param start 起始顶点
	 * @param end   结束顶点
	 * @return 顶点start到end的路径，如果不可达，则返回空数组
	 */
	public Integer[] bfs(int start, int end) {
		if (start == end) {
			return new Integer[] { start, end };
		}

		boolean[] visited = new boolean[v]; // 标记顶点是否访问，true为已访问
		Queue<Integer> queue = new LinkedList<>();// 记录某个顶点的所有邻接顶点
		int[] prev = new int[v];// 记录顶点访问路径
		Arrays.fill(prev, -1); // 这里假定顶点元素不为-1

		visited[start] = true;
		queue.add(start);
		while (queue.size() != 0) {
			int current = queue.poll();
			for (int next : adj[current]) {
				if (!visited[next]) {
					prev[next] = current; // 记录路径，即前一个顶点的值
					if (next == end) {
						List<Integer> path = new ArrayList<>();
						collectPath(prev, start, end, path);
						return path.toArray(new Integer[0]);
					}
				}
				visited[next] = true; // 标记该顶点已访问
				queue.add(next);
			}
		}
		return new Integer[0];
	}

	/**
	 * 深度优先搜索算法，时间复杂度O(E),E表示边数
	 * 
	 * @param start 起始顶点
	 * @param end   结束顶点
	 * @return 起点到终点的路径
	 */
	public Integer[] dfs(int start, int end) {
		boolean[] visited = new boolean[v];// 记录顶点是否访问过
		int[] prev = new int[v]; // 记录访问路径
		Arrays.fill(prev, -1); // 这里假定顶点值不会是-1

		recurDfs(start, end, visited, prev);

		List<Integer> path = new ArrayList<>();
		collectPath(prev, start, end, path);
		return path.toArray(new Integer[0]);
	}

	private void recurDfs(int current, int end, boolean[] visited, int[] prev) {
		visited[current] = true;
		if (current == end) {
			return;
		}
		for (int next : adj[current]) {
			if (!visited[next]) {
				prev[next] = current;
				recurDfs(next, end, visited, prev);
			}
		}
	}

	/**
	 * 回溯法收集顶点start到end的路径
	 * 
	 * @param prev
	 * @param start
	 * @param end
	 * @param path
	 */
	private void collectPath(int[] prev, int start, int end, List<Integer> path) {
		if (prev[end] != -1 && start != end) {
			collectPath(prev, start, prev[end], path);
		}
		path.add(end);
	}

}
